You are given an m x n grid where each cell can have one of three values:
0representing an empty cell,1representing a fresh orange, or2representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.
Example 1:
Input: grid = [[2,1,1],[1,1,0],[0,1,1]] Output: 4
Example 2:
Input: grid = [[2,1,1],[0,1,1],[1,0,1]] Output: -1 Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
Example 3:
Input: grid = [[0,2]] Output: 0 Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 10grid[i][j]is0,1, or2.
Average Rating: 4.60 (57 votes)
Solution
Approach 1: Breadth-First Search (BFS)
Intuition
This is yet another 2D traversal problem. As we know, the common algorithmic strategies to deal with these problems would be Breadth-First Search (BFS) and Depth-First Search (DFS).
As suggested by its name, the BFS strategy prioritizes the breadth over depth, i.e. it goes wider before it goes deeper. On the other hand, the DFS strategy prioritizes the depth over breadth.
The choice of strategy depends on the nature of the problem. Though sometimes, they are both applicable for the same problem. In addition to 2D grids, these two algorithms are often applied to problems associated with tree or graph data structures as well.
In this problem, one can see that BFS would be a better fit.
Because the process of rotting could be explained perfectly with the BFS procedure, i.e. the rotten oranges will contaminate their neighbors first, before the contamination propagates to other fresh oranges that are farther away.
If one is not familiar with the algorithm of BFS, one can refer to our Explore card of Queue & Stack which covers this subject.
However, it would be more intuitive to visualize the rotting process with a graph data structure, where each node represents a cell and the edge between two nodes indicates that the given two cells are adjacent to each other.
In the above graph (pun intended), as we can see, starting from the top rotten orange, the contamination would propagate layer by layer (or level by level), until it reaches the farthest fresh oranges. The number of minutes that are elapsed would be equivalent to the number of levels in the graph that we traverse during the propagation.
Algorithm
One of the most distinguished code patterns in BFS algorithms is that often we use a queue data structure to keep track of the candidates that we need to visit during the process.
The main algorithm is built around a loop iterating through the queue. At each iteration, we pop out an element from the head of the queue. Then we do some particular process with the popped element. More importantly, we then append neighbors of the popped element into the queue, to keep the BFS process running.
Here are some sample implementations.
In the above implementations, we applied some tricks to further optimize both the time and space complexities.
-
Usually in BFS algorithms, we keep a
visitedtable which records the visited candidates. Thevisitedtable helps us to avoid repetitive visits. -
But as one notices, rather than using the
visitedtable, we reuse the input grid to keep track of our visits, i.e. we were altering the status of the input grid in-place. -
This in-place technique reduces the memory consumption of our algorithm. Also, it has a constant time complexity to check the current status (i.e. array access,
grid[row][col]), rather than referring to thevisitedtable which might be of constant time complexity as well (e.g. hash table) but in reality could be slower than array access. -
We use a delimiter (i.e.
(row=-1, col=-1)) in the queue to separate cells on different levels. In this way, we only need one queue for the iteration. As an alternative, one can create a queue for each level and alternate between the queues, though technically the initialization and the assignment of each queue could consume some extra time.
Complexity
-
Time Complexity: O(N), where N is the size of the grid.
First, we scan the grid to find the initial values for the queue, which would take O(N) time.
Then we run the BFS process on the queue, which in the worst case would enumerate all the cells in the grid once and only once. Therefore, it takes O(N) time.
Thus combining the above two steps, the overall time complexity would be O(N)+O(N)=O(N)
-
Space Complexity: O(N), where N is the size of the grid.
In the worst case, the grid is filled with rotten oranges. As a result, the queue would be initialized with all the cells in the grid.
By the way, normally for BFS, the main space complexity lies in the process rather than the initialization. For instance, for a BFS traversal in a tree, at any given moment, the queue would hold no more than 2 levels of tree nodes. Therefore, the space complexity of BFS traversal in a tree would depend on the width of the input tree.
Approach 2: In-place BFS
Intuition
Although there is no doubt that the best strategy for this problem is BFS, some users in the Discussion forum have proposed different implementations of BFS with constant space complexity O(1). To name just a few, one can see the posts from @manky and @votrubac.
As one might recall from the previous BFS implementation, its space complexity is mainly due to the queue that we were using to keep the order for the visits of cells. In order to achieve O(1) space complexity, we then need to eliminate the queue in the BFS.
The secret in doing BFS traversal without a queue lies in the technique called in-place algorithm, which transforms input to solve the problem without using auxiliary data structure.
Actually, we have already had a taste of in-place algorithm in the previous implementation of BFS, where we directly modified the input grid to mark the oranges that turn rotten, rather than using an additional visited table.
How about we apply the in-place algorithm again, but this time for the role of the queue variable in our previous BFS implementation?
The idea is that at each round of the BFS, we mark the cells to be visited in the input grid with a specific
timestamp.
By round, we mean a snapshot in time where a group of oranges turns rotten.
Algorithm
In the above graph, we show how we manipulate the values in the input grid in-place in order to run the BFS traversal.
-
1). Starting from the beginning (with
timestamp=2), the cells that are marked with the value2contain rotten oranges. From this moment on, we adopt a rule stating as "the cells that have the value of the current timestamp (i.e.2) should be visited at this round of BFS.". -
2). For each of the cell that is marked with the current timestamp, we then go on to mark its neighbor cells that hold a fresh orange with the next timestamp (i.e.
timestamp += 1). This in-place modification serves the same purpose as thequeuevariable in the previous BFS implementation, which is to select the candidates to visit for the next round. -
3). At this moment, we should have
timestamp=3, and meanwhile we also have the cells to be visited at this round marked out. We then repeat the above step (2) until there is no more new candidates generated in the step (2) (i.e. the end of BFS traversal).
To summarize, the above algorithm is still a BFS traversal in a 2D grid. But rather than using a queue data structure to keep track of the visiting order, we applied an in-place algorithm to serve the same purpose as a queue in a more classic BFS implementation.
Complexity Analysis
-
Time Complexity: O(N2) where N is the size of the input grid.
In the in-place BFS traversal, for each round of BFS, we would have to iterate through the entire grid.
The contamination propagates in 4 different directions. If the orange is well adjacent to each other, the chain of propagation would continue until all the oranges turn rotten.
In the worst case, the rotten and the fresh oranges might be arranged in a way that we would have to run the BFS loop over and over again, which could amount to 2N times which is the longest propagation chain that we might have, i.e. the zigzag walk in a 2D grid as shown in the following graph.
As a result, the overall time complexity of the in-place BFS algorithm is O(N⋅2N)=O(N2).
-
Space Complexity: O(1), the memory usage is constant regardless the size of the input. This is the very point of applying in-place algorithm. Here we trade the time complexity with the space complexity, which is a common scenario in many algorithms.
April 29, 2020 9:33 AM
I get everything but the pun... can anyone explain the Graph pun?
Last Edit: April 19, 2020 4:57 PM
How about include at least two rotten oranges in example?
The first one is very easy to understand but the implementation in this particular solution is too complicated. There are more straightforward solutions for the first variant. I'll show you one below:
class Solution {
public int orangesRotting(int[][] grid) {
if(grid==null || grid.length == 0) return -1;
int count_fresh = 0;
Queue<Pair<Integer,Integer>> queue = new LinkedList();
int R = grid.length, C = grid[0].length;
for(int r = 0; r < R; r++)
for(int c = 0; c < C; c++)
if(grid[r][c] == 2) queue.offer(new Pair(r,c));
else if(grid[r][c]==1) count_fresh++;
if(count_fresh==0) return 0;
int count = 0;
int dirs[][] = new int[][]{{-1,0},{1,0},{0,1},{0,-1}};
while(!queue.isEmpty()) {
count++;
int size = queue.size();
for(int i = 0;i<size;i++){
Pair<Integer,Integer> pair = queue.poll();
int row = pair.getKey();
int col = pair.getValue();
for(int[] dir:dirs){
int r = row+dir[0];
int c = col+dir[1];
if(r<0 || r>=R || c<0 || c>=C || grid[r][c] == 0 || grid[r][c] == 2) continue;
grid[r][c] = 2;
queue.add(new Pair(r,c));
count_fresh--;
}
}
}
return count_fresh==0?count -1 : -1;
}
}
May 28, 2020 8:28 PM
Why is this not a hard problem?
May 8, 2020 5:09 AM
Shouldn't the first solution be N^2? You have to look in every cell of the grid to continue.
why do we start minutes at -1 instead of 0?
For the second solution , shouldn't it be N3 runtime? matrix search (N2) is repeated N/2 times.
I think there is another way to do this in-place with better time complexity by keeping track of newly rotten oranges at each minute. The older rotten oranges will infect whatever is in the neighborhood, and are no longer required. This way, we can repeat the process until we have no newly rotten oranges. This lets us modify the grid in-place. Here's my code in Python.
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
fresh = 0
rotten = collections.deque([])
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
rotten.append((i, j))
elif grid[i][j] == 1:
fresh += 1
minutes = 0
if fresh == 0:
return minutes
while rotten and fresh:
l = len(rotten)
while l:
l -= 1
i, j = rotten.popleft()
if i > 0 and grid[i - 1][j] == 1:
grid[i - 1][j] = 2
rotten.append((i - 1, j))
fresh -= 1
if i < len(grid) - 1 and grid[i + 1][j] == 1:
grid[i + 1][j] = 2
rotten.append((i + 1, j))
fresh -= 1
if j > 0 and grid[i][j - 1] == 1:
grid[i][j - 1] = 2
rotten.append((i, j - 1))
fresh -= 1
if j < len(grid[0]) - 1 and grid[i][j + 1] == 1:
grid[i][j + 1] = 2
rotten.append((i, j + 1))
fresh -= 1
minutes += 1
return -1 if fresh else minutes
I still dint get why we can't use a DFS in this problem statement? Granted that BFS is intuitive, the recursive nature of this problem statement got me thinking in the DFS way.
Any explanation would be appreciated.
June 8, 2020 2:06 PM
clean Javascript BFS Solution
/* BFS Solution */
var orangesRotting = function(grid, STATES=Object.freeze({FRESH: 1, ROTTEN:2}), dir=[[-1,0],[0,1],[0,-1],[1,0]]) {
let q = [], fresh = 0, min = 0;
for(let x=0; x<grid.length; x++) {
for(let y=0; y<grid[x].length; y++) {
if(grid[x][y]===STATES.ROTTEN) q.push([x, y])
else if(grid[x][y]===STATES.FRESH) fresh++;
}
}
while(q.length && fresh) {
let n = [];
while(q.length) {
let [x, y] = q.shift();
for(let [i, j] of dir) {
let xN = x+i, yN = y+j; //xN means x Next
if(grid[xN] !== undefined && grid[xN][yN] !== undefined && grid[xN][yN]===STATES.FRESH) {
fresh -= 1;
grid[xN][yN] = STATES.ROTTEN;
n.push([xN, yN]);
}
}
}
min++;
q = n;
}
return fresh == 0 ? min : -1;
}Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 10/08/2020 08:53 | Accepted | 12 ms | 13 MB | cpp |
| 10/08/2020 08:53 | Compile Error | N/A | N/A | cpp |
| 10/08/2020 08:51 | Accepted | 8 ms | 13 MB | cpp |
| 08/09/2020 13:34 | Accepted | 4 ms | 12.9 MB | cpp |
xxxxxxxxxxclass Solution {public: int orangesRotting(vector<vector<int>>& grid) { }};

